1. Field of the Invention
The present invention relates to a communication device having a traffic shaping function, and more specifically to an ATM terminal and an ATM switching system each having a traffic shaping function for a fixed length packet, and a communication device having a traffic shaping function for a variable length packet.
2. Description of the Related Art
An asynchronous transfer mode (ATM) technique for efficiently supporting various communication traffics such as voice, images, and data by using fixed length packets each called cell is widely known as a communication technology suitable for multimedia communications.
In the ATM, a user makes a contract about a transmission bandwidth with a network before cell transmission in units called VC (Virtual Connection) in advance. The contents of the contract differs according to the type of information to be transferred through each VC referred to above. In a real-time traffic for communications of an audio signal and a picture signal that demands for a low delay transfer, for example, a constant bandwidth is ensured within a line in advance and each cell is sent within the ensured bandwidth.
In xe2x80x9cThe ATM Forum TM4.0xe2x80x9d (prior art 1), a CBR (Constant Bit Rate) service category in which cells are sent within a fixed bandwidth ensured in advance according to a contract, and a VBR (Variable Bit Rate) service category in which the maximum transmission bandwidth and the average transmission bandwidth are placed under contract and cells are sent in a transmission bandwidth which varies according to the elapse of time, are shown as service classes for transferring real-time traffic data for speech and pictorial communications.
On the other hand, a computer-to-computer data communication has a problem in that when a bandwidth necessary for data transmission is ensured within a line in advance, the preserved bandwidth is occupied needlessly during a data transmission-free period because a traffic occurs on a burst basis (unexpectedly) and is terminated. The bandwidth held by the transmission line cannot be utilized effectively. In general, a burst traffic for non-real time communications does not attach much importance to the transmission delay important for communications by voice or the like. Thus, in the burst traffic communication, the transmission of each data cell is started without ensuring a required bandwidth in advance and the cells are temporarily stored at a node on which large amounts of data cells are focused. The bandwidth for the transmission line is effectively utilized. At each node, a cell for the real-time traffic is outputted in preference to a cell for the burst traffic. When the amount or rate of cells stored at the node exceeds the buffer capacity of the node, some of data cells belonging to the subsequent-incoming burst traffic are discarded.
In the prior art 1, an ABR (Available Bit Rate) service category for feeding back a congested (busy) state in a network to a cell sending terminal to thereby prevent the discarding of cells and a UBR (Unspecified Bit Rate) service category for allowing a sending terminal to continuously transmit cells so long as an empty or vacant bandwidth exists in a line in order to effectively utilize a line bandwidth are given as service classes for transferring the burst traffic cells. VC multiplexed over an ATM transmission line falls into or belongs to any of the service classes of said four categories.
From the characteristics about the delay/discarding of the respective service classes, each cell, which belongs to VC placed under the CBR service, is transferred most preferentially when traffics of a plurality of VC compete with one another at a node in the network. Priority control on the cell transfer is performed in the order of the CBR, VBR, ABR and UBR services.
A terminal (user), which takes advantage of the respective CBR, VBR and ABR services, makes a contract with a network, which is related to a transmission bandwidth such as the maximum transmission bandwidth, prior to its communication on the network. In the communication of the UBR service class, there are two cases: one in which a user makes a contract related to the transmission bandwidth (e.g., the maximum transmission bandwidth) and another in which no contract is done. In a public ATM network, a flow rate of cells transmitted from a terminal is monitored at an entrance of the network so as to detect VC which violates a contracted bandwidth. A marking indicative of each cell to be discarded upon the occurrence of congestion, for example, is effected on each cell which belongs to the violated VC. Such monitoring of each cell placed under violation of the contract is called UPC (Usage Parameter Control).
When a cell is discarded in the course of a transmission line, it is normally recognized by the receiving terminal that the cell has been discarded. Since, in this case, the receiving terminal requests each of transmitting terminals to re-send the discarded information and hence the transmitting terminal re-sends the information, the finally failure-free information can be sent to the corresponding receiving terminal. However, the discarding of cells in the ATM network could lead to a great delay in the transmission of the information and the occurrence of the secondary additional congestion by the re-sent cells. Thus, it is important that each transmitting terminal controls the transmission of cells at a cell flow rate set according to each contracted bandwidth so that the cells are not determined as the violated cells by the UPC function held by the network. Such a cell flow-rate control function is called traffic shaping. Incidentally, the traffic shaping is necessary even for respective switching nodes or switching systems located at important points in the ATM network to accommodate or absorb fluctuations of a cell interval for each VC, which occur in the network.
As a communication device or apparatus provided with the aforementioned traffic shaping function, there is known, for example, xe2x80x9cCell flow controller and ATM communication networkxe2x80x9d described in Japanese Unexamined Patent Publication No. Hei 6-315034 (prior art 2). When a relay node in an ATM network sends out each received cell entering with a bandwidth exceeding a contracted value to an output line with the same bandwidth as upon its reception, the cells are excessively sent out to the output line, thus causing a possibility that the cells will be discarded due to the UPC function at other nodes on a transmission route or line. Therefore, the prior art 2 has proposed that a memory for temporarily storing cells is provided in the cell flow controller and the cells received over the contracted bandwidth are temporarily stored in the memory and read out in accordance with the contracted bandwidth. However, while the prior art 2 has been described about a cell sending-interval control function using a buffer memory, which is necessary at the minimum to perform traffic shaping, it does not disclose such information as a specific device configuration, the required capacity of memory, and a process time, which is necessary for implementing the invention.
As another known technique related to the traffic shaping, there is known xe2x80x9cTraffic shaping devicexe2x80x9d described in Japanese Unexamined Patent Publication No. Hei 9-307566 (prior art 3). In the prior art 3, the estimated sending time of the next cell is managed by a binary tree structure for each VC, and VC for which cells are transmitted in top priority is selected in a short processing time of the order of log2 [number of VC] by special sorting using the result of previous sorting. According to the prior art 3, the time required to select a cell to be next transmitted can be greatly shortened using a memory having reduced capacity.
As bandwidth contracts for taking advantage of a public ATM network, there are known a contract made in VC units and a contract made in units of VP (Virtual Path) comprised of bundles of a plurality of VC. The bandwidth contract given in the VP units is normally made for each positions of the partners to communicate therewith. When a terminal 300 communicates with terminals 1901, 1902 and 1903 through a public ATM network 340 as shown in FIG. 19 by way of example, bandwidth contracts are made for each VP for connecting the terminal 300 to the partner terminals. Namely, for example, a contract related to a bandwidth of 90 Mbps, a contract related to a bandwidth of 30 Mbps and a contract related to a bandwidth of 30 Mbps are respectively made to VP(0)210 lying between the terminal 300 and the terminal 1901, VP(1)220 lying between the terminal 300 and the terminal 1902, and VP(2)230 lying between the terminal 300 and the terminal 1903. These VP(0) through VP(2) are tied up in a bundle on a line of 150 Mbps connecting between the terminal 300 and an ATM switch 341.
FIG. 2 is a conceptional diagram showing the relationship between a line 200 lying between the terminal 300 and the ATM switch 341 shown in FIG. 19 and VP and VC multiplexed over the line.
In FIG. 2, three VC211, 212 and 213 are tied up in a bundle within VP(0) 210 of 90 Mbps, two VC 221 and 222 are tied up in a bundle within VP(1) 220 of 30 Mbps, and two VC 231 and 232 are tied up in a bundle within VP(2) 230 of 30 Mbps, respectively.
As to the contracts carried out in the VP units, the network management side monitors only whether each traffic keeps the contract bandwidth set for each VP. Namely, in FIG. 19, the UPC function of the ATM switch 341 located at the entrance of the public ATM network 340 monitors a contract violation in each VP unit over the line 200 and takes measures such as marking, cell discarding, etc. against each violated cell, but does not monitor each individual bandwidths in VC units bundled within each of said VPs.
When the violated cell is discarded owing to the action of the UPC function, the large delay occurs in the transfer of the information and the additional congestion occurs due to the re-sending of each cell as described above. It is therefore desirable that even each transmitting terminal is provided with a traffic shaping function (hereinafter called xe2x80x9cVP shapingxe2x80x9d) for sending cells while keeping the contracted VP bandwidth.
When, for example, a traffic shaping device or shaper of the terminal 300 or ATM switch 341 sends each received cell to its corresponding output line while a reception sequence is being kept as it is although the bandwidth for each VC in VP is not monitored on the network side, the assurance of the bandwidth for the real-time traffic for the voice and pictorial communications and the low delay transfer cannot be implemented as the entire network. A traffic shaping function (hereinafter called xe2x80x9cVC shapingxe2x80x9d) for effecting bandwidth control in VC units and priority control set according to the service classes on each individual VC bundled in one VP is required to transfer each cell at the real-time traffic with the low delay as in the case of the CBR and VBR services.
However, the prior art 2 and the prior art 3 have described the shaping function for either VP or VC and do not disclose, similar to the prior art 3, the traffic shaping technique which simultaneously perform shaping for both VP and VC.
A first object of the present invention is to provide a communication device, an ATM terminal or an ATM switching system having a traffic shaping function, which is capable of controlling contracted bandwidths for VP and bandwidths set every VC multiplexed within the VP and effectively using a bandwidth for a transmission line and each bandwidth for each VP over the transmission line.
A second object of the present invention is to provide a traffic shaping device or shaper, an ATM terminal or an ATM switching system capable of shaping traffics on a plurality of output lines by one device.
A third object of the present invention is to provide a communication device, an ATM terminal or an ATM switching system having a traffic shaping function for a packet sending terminal or packet switch, which is capable of controlling a bandwidth for each packet within a bandwidth contracted with a network for each variable length packet while keeping the contracted bandwidth to take advantage of the in-contracted bandwidth and a bandwidth for a line.
With a view toward simultaneously performing both traffic shaping for VP and VC, it is necessary to provide traffic shaping circuits for VP and VC and monitor whether both the traffic shaping circuits are in a cell transmission-allowed state, that is, both the circuits fall into an estimated sending time. The use of the system for managing each estimated sending time with the binary tree structure described in the prior art 3 allows the implementation of selecting VP to be sent most preferentially in all VP or of selecting VC to be sent in top priority in a plurality of VCs within the same VP. However, the situation that if the estimated sending times are independently calculated, then transmission-permitted VC does not exist within the VC even if VP is in a transmission-allowed state (falls into an estimated sending time), can happen. In this case, each cell can be transmitted by reducing the bandwidth for self VP or decreasing the bandwidth for the other VP. In either case, however, the bandwidth for a communication path or line and the bandwidth for contracted VP cannot be utilized effectively. It is thus necessary to consider the estimated sending time as for VP and the estimated sending time as for VC in cooperation with each other.
The provision of traffic shaping devices every line interfaces leads to an increase in the device cost when traffic shaping is effected on a large number of low-speed lines. Thus, if the traffic shaping can be effected on a plurality of output lines by one traffic shaping device, then the traffic shaping for the large number of lines can be carried out at low cost.
The problem is not specialized on the traffic shaping for ATM cells having the fixed length. Consider where a plurality of networks are connected to one another through the use of a shared line or link as in the case of an internet or the like, and the shared line is contracted every those networks. Networks given in such a configuration are shown in FIG. 18.
In FIG. 18, a network-A 1810 and a network-a 1820 are in possession of a provider A, and terminals 1811 and 1821 are defined as users for the provider A. Similarly, a network-B 1830 and a network-b 1840 are in possession of a provider B, and terminals 1831 and 1841 are defined as users for the provider B. Further, the networks-A, networks-a, networks-B and networks-b are respectively connected to a network C 1800 by routers. The providers A and B make contracts about sending bandwidths with the network C respectively, and shares the use of a shared line or link 1801 in the network C.
When the terminals 1811 and 1821 and the terminals 1831 and 1841 communicate with one another under such a network environment, it is desirable that while the bandwidth contracted in the shared line which corresponds to VP described in ATM is being kept, priorities are provided every packets transferred within the contracted bandwidth (e.g., a packet for TELNET takes precedence over a packet for an electronic mail) so that the bandwidth, which corresponds to VC described in ATM, can be managed. As the network forms, various operation forms are considered such as the sharing of a long-distance communication line by a plurality of enterprises or companies or the case where it is desired to manage traffics every departments and sections even in the same enterprise, etc. as well as the sharing of the line by providers. It is thus necessary to implement the network forms in form coping with them.
In order to achieve the above objects from the consideration, a communication device according to the present invention comprises a first estimated sending time calculation unit for calculating a first estimated cell sending time for sending a cell with a bandwidth contracted for each connection, a second estimated sending time calculation unit for calculating a second estimated cell sending time for sending a cell with bandwidth contracted for each connection bundle obtained by collecting a plurality of the connections, and means for selecting either the use of the second estimated cell sending time or the use of the first estimated cell sending time upon transmission of each cell. Since the first estimated cell sending time and the second estimated cell sending time can be used as needed, the contracted bandwidth can be kept.
In order to achieve the first through third objects from the above consideration, the present invention provides a traffic shaping device or shaper which performs shaping in multistage form.
Namely, in order to achieve the first object, the present invention provides a traffic shaper which is installed within a terminal or exchange switch connected to an ATM network. The traffic shaper comprises a cell buffer for temporarily storing each received cell therein, a first estimated sending time calculation unit for calculating a first estimated cell sending time at which a sending interval set according to a bandwidth contracted for each VC is kept, a first sorting unit for selecting VC earliest in the first estimated cell sending time calculated by the first estimated sending time calculation unit, a sending controller for determining whether the transmission of a cell which belongs to VC selected by the first sorting unit, is allowed, reading out the corresponding cell from the cell buffer when the transmission of the cell is allowed, and sending it therefrom, a second estimated sending time calculation unit for calculating a second estimated cell sending time at which a sending interval set according to a bandwidth contracted for each VP is kept, and a second sorting unit for selecting VP earliest in the second estimated cell sending time calculated by the second estimated sending time calculation unit. The sending controller has a function of determining whether each cell which belongs to VP selected by the second sorting unit, may be sent, determining, when the transmission of the cell is allowed, whether the cell belonging to the VC selected by the first sorting unit may be sent, reading out the corresponding cell from the cell buffer when the transmission of the cell is allowed, and sending it therefrom.
In order to perform priority control between a plurality of service classes in VP, in the traffic shaper of the present invention, the first sorting unit has a function of selecting VC earliest in the first estimated cell sending time from each group of VCs each having the same priority and lying within the respective VPs, and the sending controller has a function of determining whether each cell belonging to VP selected by the second sorting unit may be sent, and sending, when the transmission of the cell is allowed, a cell which is placed in a transmission-allowed state and belongs to VC given the highest priority, from VC selected every priorities by the first sorting unit.
Further, according to the present invention, a decision bit indicative of whether a transmission-wait cell exists within the cell buffer, is provided for each VC. A decision bit indicative of whether a transmission-wait cell exists within the cell buffer, is also provided for each VP.
Furthermore, the first sorting unit or circuit is provided with means for managing each first estimated cell sending time and the cell presence decision bits by a binary tree structure and selects VC to be transmitted in top priority using the past result of sorting. On the other hand, the second sorting unit or circuit is provided with means for managing each second estimated cell sending time and the cell presence decision bits by a binary tree structure and selects VP to be sent in top priority using the past result of sorting.
The second estimated sending time calculation unit may be provided with a time reviser circuit for using a first estimated cell sending time as a second estimated cell sending time when the first estimated cell sending time for each VC selected by the first sorting unit is in future ahead of the second estimated cell sending time calculated by the second estimated sending time calculation unit and the cell-presence decision bit for VC selected by the first sorting unit is set, whereby the estimated sending time for VP and the estimated sending time for VC can be matched with each other.
Further, when the priority control is being performed between the service classes in VP, the second estimated sending time calculation unit may be provided with a time reviser. The time reviser does not change the second estimated cell sending time when the cell-presence decision bits are not set to all VC selected every priorities by the first sorting unit, by using a first estimated cell sending time as a second estimated cell sending time, when the first estimated cell sending time for VC earliest in the first estimated cell sending time among VC selected every priorities by the first sorting unit and to which cell-presence decision bits are set, and is in future ahead of the second estimated cell sending time calculated by the second estimated sending time calculation unit. In this case, the second estimated sending time calculation unit is provided with a function of resetting a cell-presence decision bit to the corresponding VP, when the cell-presence decision bits are not set to all VC selected every priorities in the given VP by the first sorting unit, and setting a cell-presence decision bit to the corresponding VP, when the cell-presence decision bit is set to any of VC selected every priorities in given VP by the first sorting unit. It is thus possible to create the situation that a transmission-wait cell exists assuredly in VC lying within VP selected by the second sorting circuit.
Further, the process executed by the first sorting circuit and the process executed by the second sorting circuit can be also done in parallel to shorten the time required to perform the sorting process.
The second object can be achieved by providing the traffic shaper of the present invention as a trunk attached to the exchange switch and replacing the VP with a line (low-speed line).
In the present invention, for achieving the third object, a packet sending terminal or packet switching system is provided with a traffic shaper which comprises a packet buffer for temporarily storing each packet received in packet form therein, a first estimated sending time calculation unit for calculating a first estimated packet sending time at which a sending interval set according to a bandwidth determined for each packet priority is kept, a first sorting unit for selecting a packet priority earliest in the first estimated packet sending time calculated by the first estimated sending time calculation unit, a second estimated sending time calculation unit for calculating a second estimated packet sending time at which a sending interval set according to a bandwidth contracted for each packet transfer destination is kept, a second sorting unit for selecting a packet destination earliest in the second estimated packet sending time calculated by the second estimated sending time calculation unit, and a sending controller for determining whether a packet which belongs to each packet destination selected by the second sorting unit may be sent, determining, when the transmission of the packet is allowed, whether the packet belonging to the packet priority selected by the first sorting unit may be sent, reading out the corresponding packet from the packet buffer when the transmission of the packet is allowed, and sending it therefrom.
The traffic shaper may be provided with a function of extracting packet length information described in a header of a packet when the packet is read out from the packet buffer so that the first estimated sending time calculation unit calculates a first estimated packet sending time by using a sending interval proportional to the packet length information and the second estimated sending time calculation unit calculates a second estimated packet sending time by using the sending interval proportional to the packet length information.
Further, the traffic shaper intended for use in the packet sending terminal or packet switch may be configured in the same structure as that of the traffic shaper intended for use in the aforementioned ATM sending terminal or ATM exchange switch.
Typical ones of various inventions of the present inventions have been shown in brief. However, the various inventions of the present application and specific configurations of these inventions will be understood from the following description.